package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/9 16:19
 */
public class M0408 {

    // https://leetcode-cn.com/problems/first-common-ancestor-lcci/
    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        return process(root, p, q).ans;
    }

    private static Info process(TreeNode root, TreeNode a, TreeNode b) {
        if(root == null) return new Info(false, false, null);
        Info li = process(root.left, a, b);
        Info ri = process(root.right, a, b);
        boolean fa = (root == a) || li.fa || ri.fa;
        boolean fb = (root == b) || li.fb || ri.fb;
        TreeNode ans = null;
        if(li.ans != null)
            ans = li.ans;
        else if(ri.ans != null)
            ans = ri.ans;
        else if (fa && fb)
            ans = root;
        return new Info(fa, fb, ans);
    }

    private static class Info {
        boolean fa;
        boolean fb;
        TreeNode ans;
        public Info(boolean fa, boolean fb, TreeNode ans) {
            this.fa = fa; this.fb = fb; this.ans = ans;
        }
    }

}
